package graph;

import java.util.Vector;

/**
 * O(v*e) Single source shortest path bellman-ford solution
 * 
 * @author yinzichen
 * 
 */
class BellmanFord {

	public int[] bellmanFord(Vector<Vector<Integer[]>> adj, int vertexNum,
			int source) {
		int[] d = new int[vertexNum];
		for (int i = 0; i < vertexNum; ++i)
			d[i] = Integer.MAX_VALUE;
		d[source] = 0;
		for (int i = 0; i < vertexNum; ++i) {
			boolean relax = false;
			for (int u = 0; u < vertexNum; ++u) {
				for (Integer[] v : adj.get(u)) {
					if (d[u] != Integer.MAX_VALUE && d[v[0]] > d[u] + d[v[1]]) {
						d[v[0]] = d[u] + d[v[1]];
						relax = true;
					}
				}
			}
			if (!relax) {
				return d;
			}
		}
		return null;
	}

}
